In employing electronic document processing it is frequently necessary, because of the quantity of data and to simplify subsequent processing, to convert electronic grey scale image data to black and white. In doing this, only text and numbers should be left as black and white information and not background patterns or pre-printed dropout colors, in order to obtain good legibility or to make it possible to effect subsequent electronic processing. For this it is necessary to be able to distinguish between the foreground containing information and the background, which generally contains no information but is structured, for example for safety or design reasons. If it is possible to distinguish between a foreground and a background, this allows the background to be removed, that is, suppression or cancellation of the background, in order to leave the foreground information.
For more certain subsequent processing of the foreground information it is necessary, in particular, to ensure that no component of the background flows into the foreground as an undesired artefact where it may lead to erroneous interpretations.
Black and white pictures, which should satisfy the requirements for subsequent electronic processing, frequently cannot be produced by the processes known from the current state of the art for background removal if the document has a highly structured background, as is the case for security reasons, for example, with the Eurocheque or an identity card. Highly structured backgrounds are generally backgrounds characterised by high contrasts which are preferably linear or like writing and exhibit structure dimensions which are of the same order as the dimensions of the written entry.
As an example of a document with a highly structured background FIG. 1 shows the currency and amounts field of a Eurocheque in grey scale representation. FIG. 2 shows the grey scale distribution along a horizontal line in FIG. 1. For this, the line was placed in the region between the handwritten and the machine-printed entries in the currency and amount field in such a way that it did not cut the entries. High values (in the "white" direction) represent a clear grey value and low values (in the "black" direction) represent dark grey values. With a conventional use of 256 grey values, grey value 0=black and grey value 255=white.
As can be seen from FIG. 2, the grey values of the background (not the frame) extend uniformly to a particular limit (threshold) which they generally, with a few exceptions such as, for example, as a result of framing or through image distortion, do not fall below. This results from the printing technology in manufacture in which the color saturation can be effectively controlled. This is generally also desired, otherwise the entries are also difficult for humans to read or may even become unreadable. The excursions below the threshold value in the "black" direction which can be clearly seen in FIG. 2 arise from the frame and the dividing line between the currency and the amount fields.
The grey value of the (handwritten and machine printed) entries, caused by the subtractive color behaviour of the most used printers, in each case lies below this threshold, however, often only very slightly. Consequently, the contrast with the background is considerably less pronounced than the contrast within the background. Subtractive colour behaviour in general means that additionally applied color pigments remove further colour components from the spectrum, i.e. that the grey value becomes darker overall.
Known methods for black and white conversion employ a background threshold value, the light-dark contrast or criteria such as the line width or the standard deviation of adjacent grey values. Contrast methods are generally not suitable for use in the field of applications described above of documents with a highly structured background since the contrast change in the background can be more pronounced than between the background and the entries. In the same way the evaluation of the line width is often unsuitable since the background structure often has a linear structure as can be seen in the example of the Eurocheque in FIG. 1.
From the printing technology properties it follows that the use of threshold value methods should give optimal results. Threshold value methods mean those methods in which the grey value is divided into classes which are limited by the threshold values concerned. However, the difficulties here lie in the correct and optimal determination of the threshold value. The threshold value is frequently calculated from the histogram of the grey values in accordance with various algorithms which should lead to the best possible black and white image. In the literature, these threshold value processes are also referred to as "thresholding" processes.
A review of the known processes can be found in "A Survey of Thresholding Techniques" by P. K. Sahoo, S. Soltani and A. K. C. Wong, in Computer Vision, Graphics and Image Processing, 41, 233-260, 1988. A distinction is made there between histogram transformation methods, which alter the shape of the histogram to determine the threshold value and algorithms for calculating the threshold value. The most important of the methods represented by Sahoo et al. are briefly discussed below in relation to their use for documents with highly structured backgrounds.
Histogram transformation methods:
The methods mentioned by Sahoo et al. for improving the histograms by means of edge operators cannot be used for highly structured backgrounds since the method does not differentiate between the edges of the background and those of the entry. The standard deviation of adjacent grey values is even less suitable for changing the histogram, since here too not only the entry but more particularly the background leads to an increased value of the standard deviation. PA1 The known "Mode and Concavity" methods likewise cannot be successfully employed for documents with highly structured backgrounds, since the highly structured background often produces a number of modes and concavities in the histogram of the grey values, so that unambiguous allocation to background and foreground is not possible. PA1 The "Otsu Method" is also unusable, since this algorithm divides the picture point into classes by maximizing the interclass variance and it is not known in advance how many classes it will give and which of them contains the information sought. PA1 The known entropy method attempts to calculate the threshold value in such a way as to maximize the data content of black and white image. However, since distinction is not made between the data contents of the background and the entry, this method too cannot be considered in the case of documents with highly structured backgrounds. PA1 1) Method with a dynamic threshold, which leads, however, to results as shown in FIG. 6, and PA1 2) a method which evaluates the line width, but is, however, unsuitable for documents with a highly structured background.
Algorithms for calculating the threshold value:
Supplementary literature to that of Sahoo et al. discusses methods and other known methods can also be found in the following sources:
In J. M. White, G. D. Rohrer, "Image Thresholding for Optical Character Recognition and other Applications Requiring Character Image Extraction", IBM J. Res. Development Vol.27 No.4 July 83 two methods are described for black and white conversion:
"Greyscale Assist for Machine Recognition of Courtesy Amount on Cheques", IBM Technical Disclosure Bulletin Vol.34 No.5 October 1991, pp. 374-377 describes a method which uses two images of different resolutions in order to select the threshold value.
In N. Otsu, "A Threshold Selection Method from Grey Level Histograms", IEEE Transactions on Systems, Man and Cybernetics, Vol. SMC-9 January 1979, pp. 66-67 the Otsu Method is presented.
T. Kurita, N. Otsu and N. Abdelmalek in "Maximum Likelihood Thresholding based on Population Mixture Models", Pattern Recognition, Vol.25 No. 10, 1231-1240, 1992, discuss the Otsu Method and applied methods.
M. A. Sid-Ahmed in "A Hardware Structure for the automatic selection of Multi-Level Thresholds in Digital Images", Pattern Recognition, Vol.25 No.12, 1517-1528, 1992, discusses a further development of the Otsu Method.
In C. K. Lee, C. H. Li, "Adaptive Thresholding via Gaussian Pyramid", China 1991, International Conference on Circuits and Systems June 1991, Shenzhen, China, a further development of the entropy method is discussed.
None of the above-listed known methods is capable of solving satisfactorily the problem of a highly structured background or providing satisfactory images which meet the requirements for subsequent electronic processing.